package now_coder.two_pointer.solutions;

import java.util.Properties;

public class NCSolution42 {

    /*
     * 接雨水问题
     *
     * 接雨水问题一个最基本的解题思路就是：算出每一个柱子左侧各个柱子中的最大值 lm，以及右侧各个柱子的最大值 rm，然后取这两个中的最小值 minmax，
     * 然后使用 minmax 减去当前柱子的高度，求出来的就是当前柱子可以储水块数。然后依次遍历每一根柱子，都按照上述方法进行求解。
     *
     * 我们可以使用暴力法进行求解，这样复杂度为 O(N^2)，我们可以使用动态规划算法进行优化。使用 dp[n][2] 数组来记录每一个柱子左右侧的柱子的
     * 最大高度。其中 dp[i][0] 表示左侧柱子 [0...i] 的最大高度，而 dp[i][1] 表示右侧柱子 [i...length-1] 的最大高度。求解的过程如下：
     *
     * 1.求解左侧柱子的最大值时，从 0 开始遍历，dp[i][0] = max(height[i], dp[i - 1][0])
     * 2.求解右侧柱子的最大值时，从 length - 1 开始遍历，dp[i][1] = max(height[i], dp[i + 1][1])
     */
}
